Transfer-Matrix Methods meet Ehrhart Theory

摘要

Transfer-Matrix Methods originated in physics where they were used to countthe number of allowed particle states on a structure whose width $n$ is aparameter. Typically the number of states is exponential in $n.$ One moremathematical instance of this methodology is to enumerate the proper vertexcolorings of a graph of growing size by a fixed number of colors. In Ehrhart theory, lattice points in the dilation of a fixed polytope by afactor $k$ are enumerated. By inclusion-exclusion, relevant conditions on howthe lattice points interact with hyperplanes are enforced. Typically the numberof points are (quasi-) polynomial in $k.$ The text-book example is that for afixed graph, the number of proper vertex colorings with $k$ colors ispolynomial in $k.$ This paper investigates the joint enumeration problem with both parameters$n$ and $k$ free. We start off with the classical graph colorings and thenexplore the common situations in combinatorics related to Ehrhart theory. Weshow how symmetries can be explored to reduce calculations and explain theinteractions with Discrete Geometry.